package java_0220.bin_tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 基础二叉树实现
 * 使用左右孩子表示法
 */
public class MyBinTree {
    private static class TreeNode{//创建内部类
        char val;
        //左子树根节点
        TreeNode left;
        //右子树根节点
        TreeNode right;
        public TreeNode(char val){
            this.val=val;
        }
    }

    /**
     * 创建一个二叉树，返回根节点
     * @return
     */
    public static TreeNode build(){
        TreeNode nodeA=new TreeNode('A');
        TreeNode nodeB=new TreeNode('B');
        TreeNode nodeC=new TreeNode('C');
        TreeNode nodeD=new TreeNode('D');
        TreeNode nodeE=new TreeNode('E');
        TreeNode nodeF=new TreeNode('F');
        TreeNode nodeG=new TreeNode('G');
        TreeNode nodeH=new TreeNode('H');
        nodeA.left=nodeB;
        nodeA.right=nodeC;
        nodeB.left=nodeD;
        nodeB.right=nodeE;
        nodeE.right=nodeH;
        nodeC.left=nodeF;
        nodeC.right=nodeG;
        return nodeA;
    }

    /**
     * 先序遍历：根左右
     * 传入一个二叉树根节点，就可以按照以先序遍历的方式输出节点值
     * @param root
     */
    public static void preOrder(TreeNode root){
        //边界条件-判空
        if(root==null){
            return;
        }
        //先打印根节点的值
        System.out.print(root.val+" ");
        //按照先序遍历的方式递归访问左树
        preOrder(root.left);
        //按照先序遍历的方式递归访问右树
        preOrder(root.right);
    }

    /**
     * 中序遍历：左根右
     * 传入一棵二叉树的根节点，就能按照中序遍历的方式来输出结果集
     * @param root
     */
    public static void inOrder(TreeNode root){
        if(root==null){
            return;
        }
        //先递归访问左子树
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    public static void postOrder(TreeNode root){
        if(root==null){
            return;
        }
        //先递归访问左子树
        postOrder(root.left);
       //再递归访问右子树
        postOrder(root.right);
        //打印根节点
        System.out.print(root.val+" ");
    }


    /**
     * 传入一棵二叉树的根节点，就能统计出当前二叉树中一共有多少个节点，返回节点数
     * 此时的访问就不再是输出节点值，而是统计节点个数
     * @param root
     * @return 当前二叉树的节点个数
     */
    //递归方式
    public static int getNodes(TreeNode root){
        if(root==null){
            return 0;
        }
        //当前根节点不为空，说明当前根节点要统计一次
        //然后加上左右子树的节点数就是整棵树的节点数
        return 1+getNodes(root.left)+getNodes(root.right);

    }
    //非递归方式
    /**
     * 使用层序遍历来统计当前数中的节点个数
     * @param root
     * @return
     */
    public static int getNodesNonRecursion(TreeNode root){
        if(root==null){
            return 0;
        }
        int size=0;
        Deque<TreeNode> queue=new LinkedList<>();
        queue.offer(root);//根节点先入队
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();//取出队首元素
            //此处的访问操作就是统计节点个数
            size++;
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            if(cur.right!=null){
                queue.offer(cur.right);
            }
        }
        return size;
    }
    /**
     * 求一棵二叉树叶子节点的个数
     * 传入一棵二叉树根节点，就能统计出当前二叉树叶子节点个数
     * @param root
     * @return
     */
    public static int getLeafNodes(TreeNode root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            //说明二叉树只有根节点，这个根节点就是叶子节点
            return 1;
        }
        //当前数不为空且存在子树，则返回子树的叶子节点数
        return getLeafNodes(root.left)+getLeafNodes(root.right);
    }
    //非递归写法-层序遍历统计叶子节点个数
    public static int getLeafNodesNonRecursion(TreeNode root){
        if(root==null){
            return 0;
        }
        int size=0;
        Deque<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();//队首出队
            if(cur.left==null&&cur.right==null){
                size++;
                continue;//直接进入下一次循环，因为叶子节点不可能存在左右孩子，就不用再走下面的判断了
            }
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            if(cur.right!=null){
                queue.offer(cur.right);
            }
        }
       return size;
    }
    /**
     * 判断当前二叉树中是否包含指定元素val
     * 若存在返回true,否则返回false
     * @param val
     * @return
     */
    public static boolean contains(TreeNode root,char val){
        if(root==null){
            return false;
        }
        if(root.val==val){
            return true;
        }
        //二叉树不为空且根节点值不是val，在子树中继续寻找
        return contains(root.left,val)||contains(root.right,val);
    }

    /**
     * 传入一个以root为根节点的二叉树，求出该树的高度
     * @param root
     * @return
     */
    public static int height(TreeNode root){
        if(root==null){
            return 0;
        }
        return 1+Math.max(height(root.left),height(root.right));
//        return 1+(height(root.left)>height(root.right)?height(root.left):height(root.right));//法2
//        int leftHeight=height(root.left);//法1
//        int rightHeight=height(root.right);
//        int max=Math.max(leftHeight,rightHeight);
//        return 1+max;

    }

    /**
     * 求出以root为根节点的二叉树第k层节点个数
     * @param root
     * @param k
     * @return
     */
    public static int getKLevelNodes(TreeNode root,int k){
        if(root==null||k<=0){
            return 0;
        }
        if(k==1){
            return 1;
        }
        //二叉树不为空且k>=2
        //以root为根节点的第k层=以root.left为根节点的k-1层+以root.right为根节点的k-1层
        return getKLevelNodes(root.left,k-1)+getKLevelNodes(root.right,k-1);
    }
    public static void main(String[] args) {
        TreeNode root=build();
//        System.out.println("前序遍历的结果为：");
//        preOrder(root);
//        System.out.println();
//        System.out.println("中序遍历结果为：");
//        inOrder(root);
//        System.out.println();
//        System.out.println("后序遍历结果为：");
//        postOrder(root);
//        System.out.println("当前二叉树一共有"+getNodes(root)+"个节点数");
//        System.out.println("当前二叉树一共有"+getNodesNonRecursion(root)+"个节点数");
        System.out.println("当前二叉树一共有"+getLeafNodes(root)+"个叶子节点");
        System.out.println("当前二叉树一共有"+getLeafNodesNonRecursion(root)+"个叶子节点");
//        System.out.println(contains(root,'E'));
//        System.out.println(contains(root,'O'));
//        System.out.println("当前二叉树高度为"+height(root));
        System.out.println("当前二叉树第三层节点个数为："+getKLevelNodes(root,3));
    }
}
